package huawei.window;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class J239 {
    public static void main(String[] args){
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3)));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        /**
         * 思路: 用队列存储前k个元素,不断更新,取最大值
         * 求最大值可知,放入一个值x,前面<x,值不再影响结果.
         * 构造单调递减队列.队头为当前元素的最大值.
         * 更新数据式,注意判断什么时候队首元素,不再范围内,及时移除
         */
        // 单调栈+滑动窗口
        int[] maxes = new int[nums.length-k+1];
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while (stack.size()>0&&nums[i]>stack.getLast()){
                stack.removeLast();
            }
           stack.add(nums[i]);

            // 控制窗口长度
            if(i>=k-1){
                maxes[i+1-k]=stack.getFirst();
                if(stack.getFirst()==nums[i+1-k]){
                    stack.removeFirst();
                }
            }
        }

        return maxes;
    }
}
